/**
 * 三数之和
 *
 * 给定一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a ，b ，c ，
 * 使得 a + b + c = 0 ？请找出所有和为 0 且 不重复 的三元组。
 *
 * 示例 1：
 * 输入：nums = [-1,0,1,2,-1,-4]
 * 输出：[[-1,-1,2],[-1,0,1]]
 *
 * 示例 2：
 * 输入：nums = []
 * 输出：[]
 *
 * 示例 3：
 * 输入：nums = [0]
 * 输出：[]
 */

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * 1. 可以直接暴力枚举, 先固定第一个数, 再固定第二个数, 最后枚举第三个数, 暴力求解...
 * 时间复杂度 : O(n^3)
 * 空间复杂度 : O(n)
 *
 * 2. 其实这题的难点不在与枚举出所有的数, 而是在于不能有重复的组合出现, 这就让我们在每次枚举数的时候要判断是否在之前
 * 出现过一样的数, 但数出现了这么多, 怎么来判断是否重复出现呢 ?
 * 因为题目没有要求组合的顺序, 所以我们可以先将原数组排个序, 这样一样的数字都在一起, 就好判断之前有没有出现过了
 * 注意在枚举任意数的时候都需要判断是否在之前枚举过
 * 为了避免时间复杂度过大, 我们还得想个方法来优化枚举的过程, 因为先固定一个数, 后面就变成了枚举两个数来是得他们的和为一个
 * 特值(和为 target的两个数) 这组数还有有序的, 这就简单了, 我们只需要从首位枚举数, 若和大了, 就使 right--, 若和小了, 就使 left++
 * 时间复杂度 : O(n^2)
 * 空间复杂度 : O(n^2)
 */

public class Main {
    public List<List<Integer>> threeSum(int[] nums) {

        // 排序
        Arrays.sort(nums);

        // 定义返回的 list
        List<List<Integer>> ret = new ArrayList<>();

        int n = nums.length;

        // 从尾部开始吧, 因为 i 的取值有限制, 要给另两个数留位置, 留在前面不易出错
        for (int i = n - 1; i > 1; i--) {
            // 固定一个数
            int target = nums[i] * (-1);

            // 另两个数
            int left = 0, right = i - 1;

            // 当两个下标相遇时, 就是循环出口
            while (left < right) {

                // 求出两个数的和
                int sum = nums[left] + nums[right];

                // 判断与目标数的大小
                if (sum < target) {

                    // 小一点就向左找
                    left++;

                } else if (sum > target) {

                    // 大一点就向右找
                    right--;

                } else {

                    // 相等就为找到, 将这三个数添加到 ret 中
                    ret.add(new ArrayList(Arrays.asList(nums[i], nums[left], nums[right])));

                    // 不要忘记偏移
                    left++;
                    right--;

                    // 为了不出现重复的 list , 我们需要排除想爱你同的数, 因为已经有一个数是固定的了,
                    // 所以后面有一个数与之前的相同, 就一定是重复的 list, 在值期间还要保持数组不要越界
                    while (left < right && nums[left - 1] == nums[left]) {
                        left++;
                    }

                    // 左边排完不要忘记右边
                    while (left < right && nums[right + 1] == nums[right]) {
                        right--;
                    }
                }
            }

            // 两边排完不要忘记固定的数
            while (i > 1 && nums[i - 1] == nums[i]) {
                i--;
            }
        }

        // 返回结果
        return ret;
    }
}